package org.laizili.solution.leetcode;

import java.util.LinkedList;
import java.util.List;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * <a href="https://leetcode.cn/problems/my-calendar-i/">729. 我的日程安排表 I</a>
 * <p>
 * tags: 排序; 二叉搜索树(TreeSet/TreeMap)应用;
 */
public class Problem729 {
    // brute force
    private static class MyCalendar {
        private static final int SZ = 1001;
        List<int[]> events = new LinkedList<>();

        public MyCalendar() {

        }

        // note: 这个解法其实不用维护事件顺序
        //    遍历事件数组, 验证事件不冲突直接添加到事件列表之后就好了
        //    开始时候想的复杂了
        public boolean book(int start, int end) {
            if (events.isEmpty()) {
                events.add(new int[]{start, end});
                return true;
            }
            int i = 0;
            int[] prevEvent = null;
            int len = events.size();
            for (; i < len; i++) {
                int[] event = events.get(i);
                if (prevEvent != null) {
                    if (start >= prevEvent[1] && end <= event[0]) {
                        events.add(i, new int[]{start, end});
                        return true;
                    }
                } else {
                    if (end <= event[0]) {
                        events.add(i, new int[]{start, end});
                        return true;
                    }
                }
                prevEvent = event;
            }
            if (prevEvent[1] <= start) {
                events.add(new int[]{start, end});
                return true;
            }
            return false;
        }
    }

    // 平衡二叉树维护区间顺序
    // TreeSet: 将区间重叠定义为广义的元素相等
    // 将一个事件安排在另一个事件之后就不会有冲突了
    //    定义事件重叠
    //         E1 = [s1, e1)
    //         E2 = [s2, e2)
    //         如果: e1 <= s2 || s1 >=e2 没有区间重叠
    private static class MyCalendar2 {
        private final TreeSet<int[]> events = new TreeSet<>((e1, e2) -> {
            if (e1[1] <= e2[0]) {
                // e1事件发生在e2事件之前
                return -1;
            } else if (e1[0] >= e2[1]) {
                // e1事件发生在e2事件之后
                return 1;
            } else {
                // e1事件和e2事件时间重叠
                return 0;
            }
        });

        MyCalendar2() {
        }

        public boolean book(int start, int end) {
            return events.add(new int[]{start, end});
        }
    }

    // 同上: TreeMap 实现
    private static class MyCalendar3 {
        private final TreeMap<Integer, Integer> events = new TreeMap<>();

        MyCalendar3() {
        }

        public boolean book(int start, int end) {
            Integer e1Start = events.floorKey(start);
            Integer e2Start = events.ceilingKey(start);
            if ((e1Start == null || events.get(e1Start) <= start) && (e2Start == null || end <= e2Start)) {
                events.put(start, end);
                return true;
            }
            return false;
        }
    }

    public static void main(String[] args) {
        MyCalendar3 calendar = new MyCalendar3();
        int[][] evs = new int[][]{{20, 29}, {13, 22}, {44, 50}, {1, 7}, {2, 10}, {14, 20}, {19, 25}, {36, 42}, {45, 50}, {47, 50}, {39, 45}, {44, 50}, {16, 25}, {45, 50}, {45, 50}, {12, 20}, {21, 29}, {11, 20}, {12, 17}, {34, 40}, {10, 18}, {38, 44}, {23, 32}, {38, 44}, {15, 20}, {27, 33}, {34, 42}, {44, 50}, {35, 40}, {24, 31}};
        boolean[] res = new boolean[]{true, false, true, true, false, true, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false};
        boolean[] output = new boolean[]{true, false, true, true, false, true, false, true, false, false, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false, false};
        for (int i = 0; i < evs.length; i++) {
            int[] event = evs[i];
            if (calendar.book(event[0], event[1]) != res[i]) {
                System.err.printf("%d,%d\n", event[0], event[1]);
            }
        }
    }
}
